package geekstudy.week7;

/**
 * 312. 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：83 ms, 在所有 Java 提交中击败了78.08% 的用户
 * 内存消耗：37.8 MB, 在所有 Java 提交中击败了88.26% 的用户
 *
 */
public class Week7BurstBalloons {

    public int maxCoins(int[] nums) {
        int numLength = nums.length;
        int[] coinArray = new int[numLength + 2];
        coinArray[0] = 1;
        for(int size = 0; size < numLength; size++) {
            coinArray[size + 1] = nums[size];
        }
        coinArray[numLength + 1] = 1;

        int[][] dynamicPlanning = new int[numLength + 2][numLength + 2];
        for(int f1 = numLength - 1; f1 >= 0; f1--) {
            for(int f2 = f1 + 2; f2 <= numLength + 1; f2++) {
                for(int f3 = f1 + 1; f3 < f2; f3++) {
                    dynamicPlanning[f1][f2] = Math.max(dynamicPlanning[f1][f2], coinArray[f1] * coinArray[f2] * coinArray[f3] + dynamicPlanning[f1][f3] + dynamicPlanning[f3][f2]);

                }
            }
        }

        return dynamicPlanning[0][numLength + 1];
    }
}
